﻿#include <iostream>
#include <stack>

using namespace std;

/*
get the shortest path to the specified node. Time complexity O(n^2)
　迪杰斯特拉(Dijkstra)算法思想 
　　按路径长度递增次序产生最短路径算法： 
　　把V分成两组： 
　　（1）S：已求出最短路径的顶点的集合 
　　（2）V-S=T：尚未确定最短路径的顶点集合 
　　将T中顶点按最短路径递增的次序加入到S中， 
　　保证：（1）从源点V0到S中各顶点的最短路径长度都不大于 
　　从V0到T中任何顶点的最短路径长度 
　　（2）每个顶点对应一个距离值 
　　S中顶点：从V0到此顶点的最短路径长度 
　　T中顶点：从V0到此顶点的只包括S中顶点作中间 
　　顶点的最短路径长度 
　　依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的 
　　直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和 
　　（反证法可证） 
　　求最短路径步骤 
　　算法步骤如下： 
　　1. 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值 
　　若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值 
　　若不存在<V0,Vi>，d(V0,Vi)为∝ 
　　2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S 
　　3. 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的 
　　距离值比不加W的路径要短，则修改此距离值 
　　重复上述步骤2、3，直到S中包含所有顶点，即S=T为止
*/

//Dijkstra - Shortest Path
#define INFINITY INT_MAX
#define MAX 5

// find the next shortest distance which has not been selected in set s,
// and return the vertax index for it. It is O(n) time complexity
int Choose(int *d, bool *s, int n)
{
  int min=INFINITY, pos=-1;

  for(int i=0;i<n;i++)
  {
    if(!s[i] && d[i]<min)
    {
      min=d[i];
      pos=i;
    }
  }

  return pos;
}

/*
a - graph matrix
n - vertax count
v - the specified vertax (source vertax)
d - distance between specifed vertax to current vertax
path - the shortest path (the adjacent vertax index in the shortest path)
*/
void Dijkstra(int a[MAX][MAX], int n, int v, int* &d, int* &path)
{
  // s to indicate whether the vertax has been selected
  bool *s=new bool[n];
  for(int i=0;i<n;i++)
  {
    s[i]=false;
    if(i!=v && a[v][i] )
	{
		d[i]=a[v][i];
        path[i]=v;
	}
    else
	{
		d[i]=INFINITY;
        path[i]=-1;
	}
  }

  s[v]=true;
  while(true)
  {
    int k=Choose(d,s,n);
    if(k>=0)
    {
      s[k]=true;
      for(int j=0;j<n;j++)
      {
        if(!s[j] && a[k][j] && d[k]+a[k][j]<d[j])
        {
          d[j]=d[k]+a[k][j];
          path[j]=k;
        }
      }
    }
	else
		break;
  }

  delete[] s;
}

// it is a wrapper for Dijkstra
void ShortestPath( int graph[MAX][MAX], int nodeCount, int src, int des )
{
	if(!graph||nodeCount<=0)
	{
		cout<<"Empty Graph";
		return;
	}

	if( src<0||src>nodeCount-1 ||
		des<0||des>nodeCount-1 )
	{
		cout<<"Out of Bound";
		return;
	}

	int *distance=new int[nodeCount];
	int *path=new int[nodeCount];

	(void)Dijkstra(graph, nodeCount, src, distance, path);
  
	//Print shortest-path from src to des (it is optional)
	int minPath = distance[des];
	if( minPath != INFINITY )
	{
		stack<int> pathStack;
		int cur = des;
		pathStack.push(path[cur]);
		while( path[cur] != src )
		{
			cur = path[cur];
			pathStack.push(path[cur]);
		}

		// get the path in the stack and print it
		cout<<"the shortest path is "<<minPath<<endl;
		cout<<"the path is:";
		while(!pathStack.empty())
		{
			cout<<pathStack.top()<<"->";
			pathStack.pop();
		}
		cout<<des<<endl;
	}
	else
	{
		cout<<"there is no path between vertax "<<src<<" and vertax "<<des<<endl;
	}

	delete [] distance;
	delete [] path;
}

int main(void)
{
	int graph[MAX][MAX]={{0,1,1,0,1},{0,0,0,0,1},{0,1,0,0,1},{0,0,0,0,1},{0,0,0,1,0}};
	ShortestPath(graph, MAX, 2, 3 );

	cout<<"Press any key to terminate..."<<endl;
	return getchar();
}